package java_thinking.unit_19;

import java.util.ArrayList;
import java.util.EnumSet;
import java.util.List;
import java.util.Random;

/**
 * @Desc:   EnumSet
 *      1.与枚举类型一起使用的专用 Set 实现
 *      2.枚举 set 中所有键都必须来自单个枚举类型，该枚举类型在创建 set 时显式或隐式地指定
 *      3.枚举 set 在内部表示为位向量。此表示形式非常紧凑且高效。此类的空间和时间性能应该很好，足以用作传统上基于 int
 *        的“位标志”的替换形式，具有高品质、类型安全的优势。如果其参数也是一个枚举 set，则批量操作(如 containsAll 和
 *        retainAll)也应运行得非常快。
 *      4.不允许为null 会抛出NullPointerException；
 *      5.EnumSet 是不同步的 Set<MyEnum> s = Collections.synchronizedSet(EnumSet.noneOf(MyEnum.class));
 *      6.EnumSet 内部enum实例初始个数为long，最多可应用于64个元素的enum，但是如果超过这个个数也能存储
 *        RegularEnumSet enum内部实例<=64 时使用该类存储
 *        JumboEnumSet   enum内部实例>64 时使用该类存储
 *        目的是更为高效的存储过程
 *      7.此类是 Java Collections Framework 的成员。
 *
 *      8.什么时候使用EnumSet比较恰当的，事实上当需要进行位域运算，就可以使用EnumSet提到位域，如EnumSetDemo
 *
 *      9.位向量表示集合
 *        a=[01101001]表示{0，3，5，6} 从右往左为 1 的位分别为 0、3、5、6 所以表示集合 {0，3，5，6}
 *        b=[01010101]表示{0，2，4，6} 从右往左为 1 的位分别为 0、2、4、6 所以表示集合 {0，2，4，6}
 *        a&b={01000001} 为 1 的位分比为 0、6 所以交集为 {0,6} 也就是 {0，3，5，6} 与 {0，2，4，6} 中共同存在 0 与 6 两个数字
 *
 *      10.如何用位向量表示一个十进制整数，如用int来进行位向量存储，
 *        P = 40 / 32 = 1   等同于位域运算 40 >> 5 (5来自int位数为 2^5)
 *        S = 40 % 32 = 8   快速取余数方法 40的二进制与 2^n-1 进行与操作 n取决于用什么类型的数据，int的话n=5
 *                          因为2^5=32 0-31是32位bit
 *                          即40 二进制(00101000)与 31 二进制(00011111)相与 得出二进制000 1000 即十进制8
 *        a[P] |= 1 << S    整句意思是把a[P]元素的第S+1位设置为1
 *        a[P] &= ~(1 << S) 置为0
 *        即a[1] 的 a[1][8] = 1 位向量则表示十进制 40
 *        推理过程见:https://blog.csdn.net/javazejian/article/details/71333103
 *
 *
 * @author: cww
 * @DateTime: 2019-05-25 22:31
 */

public class EnumSetTheory {
}

/**
 * 1.位域运算例
 */
class EnumSetDemo {
    //定义位域变量
    //1
    /**
     * 1
     */
    public static final int TYPE_ONE = 1 << 0 ;
    /**
     * 2
     */
    public static final int TYPE_TWO = 1 << 1 ;
    /**
     * 4
     */
    public static final int TYPE_THREE = 1 << 2 ;
    /**
     * 8
     */
    public static final int TYPE_FOUR = 1 << 3 ;

    public static void main(String[] args) {
        int type = TYPE_ONE | TYPE_TWO | TYPE_THREE | TYPE_FOUR;
        System.out.println(type);
    }
}

/**
 * 2.用enumSet集合操作位域
 */

enum Type {
    TYPE_ONE,TYPE_TWO,TYPE_THREE,TYPE_FOUR
}

class EnumSetDemo1 {
    public static void main(String[] args) {
        EnumSet set = EnumSet.of(Type.TYPE_ONE,Type.TYPE_FOUR);
        System.out.println(set);
    }
}

/**
 * 位向量实现
 */
class BitVector {
    private int count;
    /**
     * 存储元素的数组
     */
    private static int[] a;
    /**
     * 默认使用int类型
     */
    private static int BIT_LENGTH = 32;
    /**
     * 整数部分
     */
    private static int P;
    /**
     * 余数
     */
    private static int S;
    /**
     * int类型用于计算取余数的数 31
     * 2^5 - 1
     * 40 二进制(00101000)与 31 二进制(00011111)相与 得出二进制000 1000 即十进制8
     */
    private static int MASK;
    /**
     * 用于计算P的数
     * 40 / 32 等同于 40 >> 5 得出整数1
     */
    private static int SHIFT = 5;

    /**
     *  初始化位向量
     * @param count
     */
    public BitVector(int count) {
        this.count = count;
        a = new int[(count - 1)/BIT_LENGTH + 1];
        System.out.println(a.length);
        init();
    }

    /**
     * 将数组中元素bit位设置为0
     */
    public void init() {
        for (int i = 0; i < count; i++) {
            clear(i);
        }
    }

    /**
     *  获取排序后的数组
     * @return
     */
    private List<Integer> getSortedArray() {
        List<Integer> sortedArray = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            if (get(i) == 1) {
                sortedArray.add(i);
            }
        }
        return sortedArray;
    }

    /**
     * 位向量添加操作
     * @param i
     */
    public void set(int i) {
        //结果等同  P = i / BIT_LENGTH; 取整数 ①
        P = i >> SHIFT;
        //结果等同  S = i % BIT_LENGTH; 取余数 ②
        S = i & MASK;
        //赋值设置该元素bit位为1               ③
        a[P] |= 1 << S;
        //合并①②③
        //a[i >> SHIFT] |= (1 << (i & MASK));
    }

    /**
     *  RegularEnumSet 中添加枚举源码
     *     public boolean add(E e) {
     *         typeCheck(e);
     *
     *         long oldElements = elements;
     *         //这里用的long类型单一变量实现 ，((Enum)e).ordinal()通过该语句获取要添加的枚举实例的序号，然后通过1左移再与
     *         //long类型的elements进行或操作，就可以把对应位置上的bit设置为1了，也就代表该枚举实例存在。
     *         elements |= (1L << ((Enum<?>)e).ordinal());
     *         return elements != oldElements;
     *     }
     */


    /**
     * 位向量删除操作
     * @param i
     */
    public void clear(int i) {
        P = i >> SHIFT;
        S =  i & MASK;
        //把a[P]元素的第S+1个(从低位到高位)bit位设置为0
        a[P] &= ~(1 << S);
        //更优写法
        //将int型变量j的第k个比特位设置为0，即j = j & ~(1<<k)
        //a[i>>SHIFT] &= ~(1<<(i &MASK));
    }

    /**
     * 读取操作，返回1表示该bit位有值，返回 0 则无
     * @param i
     * @return
     */
    public int get(int i) {
        P = i >> SHIFT;
        S =  i & MASK;
        //Integer.bitCount()是返回指定 int 值的二进制补码表示形式的 1 位的数量
        //计算机数字的二进制表示法都是使用补码表示的
        return Integer.bitCount(a[P] & (1 << S));
    }
    public static void main(String[] args) {
        int count = 40;
        List<Integer> randoms = getRandomsList(count);
        System.out.println("排序前：");

        BitVector bitVector = new BitVector(count);
        for (Integer e : randoms) {
            System.out.print(e+",");
            bitVector.set(e);
        }
        System.out.println();
        System.out.println("sorted");
        List<Integer> sortedArray = bitVector.getSortedArray();
        System.out.println(sortedArray);
    }

    private static List<Integer> getRandomsList(int count) {
        Random random = new Random();

        List<Integer> randomsList = new ArrayList<Integer>();
        while(randomsList.size() < (count - 1)){
            //element ∈  [1,count)
            int element = random.nextInt(count - 1) + 1;
            if (!randomsList.contains(element)) {
                randomsList.add(element);
            }
        }
        return randomsList;
    }

}

